using System;
using System.Collections;
using System.Threading;

public class Sudoku
{
    static Random rand = new Random();
    static ulong MASK;
    static int N, N2, N3, N4, N6, N2_1, N4_1, qn, hi;

    static bool done;
    static Hashtable pairsHT, triplesHT;
    static int[,] tb;
    static int[, ,] tb3;
    static int[] h1, h2, h3;
    static int[] rs;
    static Set[] sets;
    static Cell[] cells;
    static int[][] subs, pairs, pairsOfSubs;
    static ulong[] subsMask, pairsMask;
    static IQ subsIQ, pairsIQ, setsIQ;
    public int[] queryResults(int x, int[] qr)
    {
        cells[(qr[0] - 1) * N2 + qr[1] - 1].mask1(1LU << (x - 1));
        if (qn < N2)
        {
            qr[1] = N * (qn % N) + (qn / N) + 1;
            qr[0] = ++qn;
            return qr;
        }
        double best = double.MinValue, tt;
        int bestk = -1, k;
    Loop:
        while ((k = setsIQ.Next()) >= 0)
            sets[k].update();
        done = false;
        while ((k = subsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int mid in subs[k])
                m |= cells[mid].mk;
            if (subsMask[k] != m)
            {
                subsMask[k] = m;
                foreach (int pid in pairsOfSubs[k])
                    pairsIQ.Add(pid);
            }
        }
        while ((k = pairsIQ.Next()) >= 0)
        {
            ulong m = 0LU;
            foreach (int sid in pairs[k])
                m |= subsMask[sid];
            if (pairsMask[k] != m)
            {
                pairsMask[k] = m;
                pairsMask[k ^ 1] = m;
                foreach (int sid in pairs[k ^ 1])
                    foreach (int mid in subs[sid])
                        if (rs[mid] == 0)
                            cells[mid].mask1(m);
            }
        }
        if (done)
            goto Loop;


        for (k = N4_1; k >= 0; k--)
            if (rs[k] == 0 && (tt = 3 * N * Count(cells[k].mk) + (k / N2) + (k % N2) + rand.NextDouble()) >= best)
            {
                best = tt; bestk = k;
            }
        if (bestk >= 0)
            return new int[] { (bestk / N2) + 1, (bestk % N2) + 1 };

        return rs;
    }

    public int[] initialize(int n)
    {
        int i, j, k, l, s, e, a, b;
        qn = 1;
        N = n;
        N2 = n * n;
        N3 = N2 * n;
        N4 = N3 * n;
        N6 = N3 * N3;
        N2_1 = N2 - 1;
        N4_1 = N4 - 1;
        MASK = 1LU << (N2_1);
        MASK = (MASK - 1) + MASK;

        pairsHT = new Hashtable(N4);
        triplesHT = new Hashtable(N4);
        rs = new int[N4];
        cells = new Cell[N4];
        for (i = N4_1; i >= 0; i--)
            cells[i] = new Cell(i);

        tb = new int[N2, N2];
        for (i = N2_1; i >= 0; i--)
            for (j = N2_1; j >= 0; j--)
                tb[i, j] = -1;
        tb3 = new int[N2, N2, N2];

        h1 = new int[N4];
        h2 = new int[N4];
        h3 = new int[N4];

        subsIQ = new IQ(2 * N3);
        pairsIQ = new IQ(4 * N3);
        setsIQ = new IQ(3 * N2);

        subs = new int[2 * N3][];
        subsMask = new ulong[2 * N3];
        pairsOfSubs = new int[2 * N3][];
        for (i = subs.Length - 1; i >= 0; i--)
        {
            subs[i] = new int[n];
            subsMask[i] = MASK;
            pairsOfSubs[i] = new int[2 * (n - 1)];
        }
        pairs = new int[4 * N3][];
        pairsMask = new ulong[4 * N3];
        for (i = pairs.Length - 1; i >= 0; i--)
        {
            pairs[i] = new int[n - 1];
            pairsMask[i] = MASK;
        }

        sets = new Set[3 * N2];
        for (i = sets.Length - 1; i >= 0; i--)
            sets[i] = new Set(i);
        for (k = N4_1; k >= 0; k--)
        {
            i = k / N2;
            j = k % N2;
            Cell c = cells[k];
            sets[i].list[j] = c;
            c.r = sets[i];
            c.rmk = ~(1LU << j);
            sets[N2 + j].list[i] = c;
            c.c = sets[N2 + j];
            c.cmk = ~(1LU << i);
            sets[a = N2 + N2 + i / n * n + j / n].list[b = (i % n) * n + (j % n)] = c;
            c.a = sets[a];
            c.amk = ~(1LU << b);
            cells[k].s1 = a = i * n + j / n;
            cells[k].s2 = b = N3 + j * n + i / n;
            subs[a][j % n] = k;
            subs[b][i % n] = k;
        }

        int d = N3 << 1;
        int[] posp = new int[pairsOfSubs.Length];
        for (k = N3 - 1; k >= 0; k--)
        {
            i = k / n;
            j = k % n;
            a = k << 1;
            for (l = 0, s = i * n, e = s + n; s < e; s++)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
            a++;
            for (l = 0, s = i / n * N2 + j, e = s + N2; s < e; s += n)
                if (s != k)
                {
                    pairs[a][l] = s;
                    pairs[d + a][l] = b = N3 + s;
                    l++;
                    pairsOfSubs[s][posp[s]++] = a;
                    pairsOfSubs[b][posp[b]++] = d + a;
                }
        }
        return new int[] { 1, 1 };
    }

    class Cell
    {
        public Cell(int k)
        {
            this.k = k;
            this.mk = MASK;
        }
        public int Result { get { return rs[k]; } }
        public override string ToString()
        {
            return rs[k] + "@[" + k + "](" + r + "," + c + "," + a + ")" + mk.ToString("X16");
        }
        public bool needUpdate = false;
        public ulong mk, rmk, cmk, amk;
        public int s1, s2, k;
        public Set r, c, a;
        public void mask1(ulong m)
        {
            if (mk != (mk & m))
            {
                mk &= m;
                //if (mk == 0)
                //    throw new Exception();
                subsIQ.Add(s1);
                subsIQ.Add(s2);
                setsIQ.Add(r.sid);
                setsIQ.Add(c.sid);
                setsIQ.Add(a.sid);
                done = true;
                needUpdate = true;
            }
        }
        public void mask(ulong m)
        {
            if (mk != (mk & m))
            {
                mk &= m;
                //if (mk == 0)
                //    throw new Exception();
                done = true;
                needUpdate = true;
            }
        }
        public void update()
        {
            if (needUpdate)
            {
                needUpdate = false;
                subsIQ.Add(s1);
                subsIQ.Add(s2);
                setsIQ.Add(r.sid);
                setsIQ.Add(c.sid);
                setsIQ.Add(a.sid);
                int i = 0;
                ulong m;
                for (m = mk ^ MASK; m != 0; m >>= 1, i++)
                {
                    if ((m & 1LU) != 0)
                    {
                        r.ps[i] &= rmk;
                        c.ps[i] &= cmk;
                        a.ps[i] &= amk;
                    }
                }
                if (((mk - 1) & mk) == 0)
                {
                    int x = First(mk);
                    rs[k] = x + 1;
                    //if (r.ps[x] == 0LU || c.ps[x] == 0LU || a.ps[x] == 0LU)
                    //    throw new Exception();
                    r.ps[x] = 0LU;
                    c.ps[x] = 0LU;
                    a.ps[x] = 0LU;
                    r.mask(this);
                    c.mask(this);
                    a.mask(this);
                }
            }
        }
    }

    class Set
    {
        public Set(int sid)
        {
            this.sid = sid;
            this.isa = sid >= (N2 + N2);
            this.list = new Cell[N2];
            ps = new ulong[N2];
            for (int i = N2_1; i >= 0; i--)
                ps[i] = MASK;
        }
        bool found2(Cell c1, Cell c2)
        {
            Pair p = new Pair(c1.k, c2.k);
            if (!pairsHT.ContainsKey(p))
            {
                pairsHT.Add(p, null);
                this.mask(c1, c2);
                if (isa)
                {
                    if (c1.r == c2.r)
                        c1.r.mask(c1, c2);
                    else if (c1.c == c2.c)
                        c1.c.mask(c1, c2);
                }
                else if (c1.a == c2.a)
                    c1.a.mask(c1, c2);
                return true;
            }
            return false;
        }
        bool found3(Cell c1, Cell c2, Cell c3)
        {
            Triple t = new Triple(c1.k, c2.k, c3.k);
            if (!triplesHT.ContainsKey(t))
            {
                triplesHT.Add(t, null);
                this.mask(c1, c2, c3);
                if (isa)
                {
                    if (c1.r == c2.r && c1.r == c3.r)
                        c1.r.mask(c1, c2, c3);
                    else if (c1.c == c2.c && c1.c == c3.c)
                        c1.c.mask(c1, c2, c3);
                }
                else if (c1.a == c2.a && c1.a == c3.a)
                    c1.a.mask(c1, c2, c3);
                return true;
            }
            return false;
        }
        public void mask(Cell c1)
        {
            ulong m = ~c1.mk;
            int i;
            for (i = 0; list[i] != c1; i++)
                list[i].mask(m);
            while (++i < N2)
                list[i].mask(m);
        }
        public void mask(Cell c1, Cell c2)
        {
            ulong m = ~(c1.mk | c2.mk);
            int i;
            for (i = 0; list[i] != c1; i++)
                list[i].mask(m);
            for (i++; list[i] != c2; i++)
                list[i].mask(m);
            while (++i < N2)
                list[i].mask(m);
        }
        public void mask(Cell c1, Cell c2, Cell c3)
        {
            ulong m = ~(c1.mk | c2.mk | c3.mk);
            int i;
            for (i = 0; list[i] != c1; i++)
                list[i].mask(m);
            for (i++; list[i] != c2; i++)
                list[i].mask(m);
            for (i++; list[i] != c3; i++)
                list[i].mask(m);
            while (++i < N2)
                list[i].mask(m);
        }
        bool hit(int a1, int a2, int a3, int i)
        {
            int a = tb3[a1, a2, a3];
            if (a > (1 << 8))
            {
                return found3(
                    list[(a >> 8) - 1],
                    list[(a & 0xff) - 1],
                    list[i]);
            }
            tb3[a1, a2, a3] = (a << 8) | (i + 1);
            h1[hi] = a1;
            h2[hi] = a2;
            h3[hi] = a3;
            hi++;
            return false;
        }

        bool hitp(int a1, int a2, int a3, int i)
        {
            int a = tb3[a1, a2, a3];
            if (a > (1 << 8))
            {
                ulong m = (1LU << ((a >> 8) - 1)) | (1LU << ((a & 0xff) - 1)) | (1LU << i);
                list[a1].mask(m);
                list[a2].mask(m);
                list[a3].mask(m);
                return found3(
                    list[a1],
                    list[a2],
                    list[a3]);
            }
            tb3[a1, a2, a3] = (a << 8) | (i + 1);
            h1[hi] = a1;
            h2[hi] = a2;
            h3[hi] = a3;
            hi++;
            return false;
        }

        public bool isa;
        public int sid;
        public ulong[] ps;
        public Cell[] list;
        public void update()
        {
            setsIQ.m[sid] = -1;
            int i;
            int a1, a2, a3, a;
            ulong m1, m2, m3;
        Loop:
            done = false;
            #region 2i
            hi = 0;
            for (i = 0; i < N2; i++)
            {
                m1 = list[i].mk;
                if (m1 == 0)
                    continue;
                //throw new Exception();
                m2 = (m1 - 1) & m1;
                if (m2 == 0)
                    continue;
                if (((m2 - 1) & m2) != 0)
                    continue;
                a1 = First(m1);
                a2 = First(m2);
                a = tb[a1, a2];
                if (a >= 0)
                {
                    if (found2(list[a], list[i]))
                        break;
                }
                else
                {
                    tb[a1, a2] = i;
                    h1[hi] = a1;
                    h2[hi] = a2;
                    hi++;
                }
            }
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (done)
                goto Loop;
            #endregion

            if (N > 4)
            {
                #region 3i
                hi = 0;
                for (i = 0; i < N2; i++)
                {
                    m1 = list[i].mk;
                    if (m1 == 0)
                        continue;
                    //throw new Exception();
                    m2 = (m1 - 1) & m1;
                    if (m2 == 0)
                        continue;
                    m3 = (m2 - 1) & m2;
                    a1 = First(m1);
                    a2 = First(m2);
                    if (m3 == 0)
                    {
                        a3 = N2;
                        while (--a3 > a2)
                            if (hit(a1, a2, a3, i))
                                goto Clear3i;
                        while (--a2 > a1)
                            if (hit(a1, a2, a3, i))
                                goto Clear3i;
                        while (--a1 >= 0)
                            if (hit(a1, a2, a3, i))
                                goto Clear3i;
                        continue;
                    }
                    if (((m3 - 1) & m3) == 0 &&
                        hit(a1, a2, First(m3), i))
                        break;
                }
            Clear3i:
                while (--hi >= 0)
                    tb3[h1[hi], h2[hi], h3[hi]] = 0;
                if (done)
                    goto Loop;
                #endregion
            }

            #region 1i & for x
            for (i = 0; i < N2; i++)
                list[i].update();
            #endregion

            #region 1x
            for (i = 0; i < N2; i++)
            {
                m1 = ps[i];
                if (m1 == 0)
                    continue;
                if (((m1 - 1) & m1) != 0)
                    continue;
                a = First(m1);
                m1 = 1LU << i;
                list[a].mask(m1);
                mask(list[a]);
            }
            if (done)
                goto Loop;
            #endregion

            #region 2x
            hi = 0;
            for (i = 0; i < N2; i++)
            {
                m1 = ps[i];
                if (m1 == 0)
                    continue;
                m2 = (m1 - 1) & m1;
                if (m2 == 0)
                    continue;
                if (((m2 - 1) & m2) != 0)
                    continue;
                a1 = First(m1);
                a2 = First(m2);
                a = tb[a1, a2];
                if (a >= 0)
                {
                    m1 = (1LU << a) | (1LU << i);
                    list[a1].mask(m1);
                    list[a2].mask(m1);
                    if (found2(list[a1], list[a2]))
                        break;
                }
                else
                {
                    tb[a1, a2] = i;
                    h1[hi] = a1;
                    h2[hi] = a2;
                    hi++;
                }
            }
            while (--hi >= 0)
                tb[h1[hi], h2[hi]] = -1;
            if (done)
                goto Loop;
            #endregion

            if (N > 4)
            {
                #region 3x
                hi = 0;
                for (i = 0; i < N2; i++)
                {
                    m1 = ps[i];
                    if (m1 == 0)
                        continue;
                    m2 = (m1 - 1) & m1;
                    if (m2 == 0)
                        continue;
                    m3 = (m2 - 1) & m2;
                    a1 = First(m1);
                    a2 = First(m2);
                    if (m3 == 0)
                    {
                        a3 = N2;
                        while (--a3 > a2)
                            if (hitp(a1, a2, a3, i))
                                goto Clear3x;
                        while (--a2 > a1)
                            if (hitp(a1, a2, a3, i))
                                goto Clear3x;
                        while (--a1 >= 0)
                            if (hitp(a1, a2, a3, i))
                                goto Clear3x;
                        continue;
                    }
                    if (((m3 - 1) & m3) == 0 &&
                        hitp(a1, a2, First(m3), i))
                        break;
                }
            Clear3x:
                while (--hi >= 0)
                    tb3[h1[hi], h2[hi], h3[hi]] = 0;
                if (done)
                    goto Loop;
                #endregion
            }

            setsIQ.m[sid] = 0;
        }
    }

    class IQ
    {
        public IQ(int n)
        {
            q = new int[n];
            m = new int[n];
            this.n = n;
        }
        public int e = 0, i = 0, n;
        public int[] m, q;
        public int Next()
        {
            if (e == i)
                return -1;
            int ret = q[e % n];
            e++;
            m[ret] = 0;
            return ret;
        }
        public void Add(int a)
        {
            if (m[a] != 0)
                return;
            m[a] = 1;
            q[i % n] = a;
            i++;
        }
    }

    struct Pair
    {
        public Pair(int a1, int a2)
        {
            this.a1 = a1;
            this.a2 = a2;
        }
        public int a1, a2;
        public override int GetHashCode()
        {
            return (a2 << 16) | a1;
        }
    }
    struct Triple
    {
        public Triple(int a1, int a2, int a3)
        {
            this.a1 = a1;
            this.a2 = a2;
            this.a3 = a3;
        }
        public int a1, a2, a3;
        public override int GetHashCode()
        {
            return (a3 << 20) ^ (a2 << 10) ^ a1;
        }
    }

    #region Static Functions
    static int Count(ulong m)
    {
        int ret = 0;
        while (m > 0)
        {
            ret++;
            m = (m - 1) & m;
        }
        return ret;
    }
    static int First(ulong m)
    {
        for (int q = 0; q < N2; q++)
            if ((m & (1LU << q)) != 0LU)
                return q;
        if (m == 0)
            throw new Exception();
        return -1;
    }
    #endregion
}